There are cases where a change is brought about in how links connecting nodes are arranged in a network (topology). The change sometimes causes that a point or an area in the network can be passed which has not been possible before, and vice versa.
If a path from any starting point to any destination point is required to be the shortest, along with a change in a topology of the path, it is necessary to calculate the shortest path after the topological change.
In a method of calculating the shortest path according to the related art, if a topology changes, all shortest paths connecting two nodes are calculated again using information on the topology after the change.
Such a shortest path calculating method is described in non-Patent Document 1. Note that the method described in non-Patent Document 1 is known as the Dijkstra's algorithm.
Of note is the fact that, in many cases, there is no difference between the shortest paths before and after the topological change. In another cases, if the shortest path connecting nodes other than nodes to be calculated has already been calculated after the topological change, there is no difference between the already-calculated shortest path and the shortest path between the nodes to be calculated.
In a method of calculating the shortest path according to the related art, the shortest path is calculated using information only on how links connecting nodes are arranged. The method according to the related art fails to use information on already-existing shortest paths, even if there is no difference between the shortest paths before and after the topological change. This disadvantageously requires all shortest paths to be recalculated, which takes a longer calculating time.
In a method of calculating the shortest path, a numerical value called a cost is generally assigned to a link connecting two nodes. The shortest path is obtained by calculating an appropriate path such that a sum of costs of links through which the path goes is minimal.
Non-Patent Document 2 discloses a technique of, if the cost of a given link is changed, calculating the shortest path after its topological change, using information on the shortest path before the topological change. The technique can solve the problem that it takes a longer calculating time to recalculate all the shortest paths as described above.
[Non-Patent Document 1] E. W. Dijkstra: A note on two problems in connexion with graphs. In Numerische Mathematik, 1(1959), S. 269-271.
[Non-Patent Document 2] B. Xiao, et al. “Dynamic update of shortest path tree in OSPF,” IEEE Parallel Architectures Algorithms and Network, pp. 18-23, May 2004.